/*
// @title: 查找算法
// @auth: 技术狼(jishulang.com)
*/
package fun

// @title: 二分查找法
// @param: nums:数组
// @return: int
// @description: 二分查找的基础是先做排序，然后做二分查找
// @date: 2024/6/11 22:32
func BinarySearch(nums []int, val int) int {
	left, right := 0, len(nums)-1

	for left <= right {
		// 防止(left + right)可能发生的整数溢出
		mid := left + (right-left)/2
		if nums[mid] == val {
			return mid
		} else if nums[mid] < val {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	// 如果没有找到值，返回-1或特定的错误指示
	return -1
}

// @title: 斐波拉契数列-递归方法
// @param: n:想要计算的斐波那契数列中的第 n 个数
// @return: int
// @description: 找出第n位数是什么，时间复杂度是n方
// @date: 2024/6/11 22:32
func FibonacciRecursion(n int) int {
	if n == 0 {
		return 0
	} else if n == 1 {
		return 1
	} else {
		return FibonacciRecursion(n-1) + FibonacciRecursion(n-2)
	}
}

// @title: 斐波拉契数列-迭代法
// @param: n:想要计算的斐波那契数列中的第 n 个数
// @return: int
// @description: 找出第n位数是什么，时间复杂度是n方
// @date: 2024/6/11 22:32
func FibonacciFind(n int) int {
	x, y, fib := 0, 1, 0
	for i := 0; i <= n; i++ {
		if i == 0 {
			fib = 0
		} else if i == 1 {
			fib = x + y
		} else {
			fib = x + y
			x, y = y, fib
		}
	}
	return fib
}
